package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

//Java：电话号码的字母组合
public class LetterCombinationsOfAPhoneNumber {
    public static void main(String[] args) {
        Solution solution = new LetterCombinationsOfAPhoneNumber().new Solution();
        List<String> strings = solution.letterCombinations("23");
        System.out.println(strings);
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        public List<String> letterCombinations(String digits) {
            // 如果输入字符串为空或长度为0，返回空列表
            if (digits == null || digits.length() == 0) {
                return new ArrayList<>();
            }

            // 创建一个映射数组，将数字映射到相应的字母
            String[] mapping = {
                    "",     // 0
                    "",     // 1
                    "abc",  // 2
                    "def",  // 3
                    "ghi",  // 4
                    "jkl",  // 5
                    "mno",  // 6
                    "pqrs", // 7
                    "tuv",  // 8
                    "wxyz"  // 9
            };

            // 初始化结果列表
            List<String> result = new ArrayList<>();
            // 开始回溯算法
            backtrack(result, digits, "", 0, mapping);
            // 返回最终结果
            return result;
        }
        /**
         * 回溯算法是一种解决问题的算法，它试图通过从可能的解决方案中逐步构建并测试这些解决方案的组件来找到问题的解决方案。如果当前的组件或步骤不会导致最终的解决方案，算法将回溯（即撤销最后的选择），
         * 尝试下一个选项。这种算法通常用于解决组合问题、排列问题、分区问题和其他复杂问题。
         * <p>
         * 回溯算法的特点和过程如下：
         * <p>
         * 路径选择：从可能的选择中选择一个选项，试图构建解决方案的一部分。
         * <p>
         * 约束条件：决定当前选择是否符合问题的约束条件。如果不符合，就放弃这个选择。
         * <p>
         * 目标达成：检查当前解决方案是否已经达到了预期的目标。如果是，记录或返回这个解决方案。
         * <p>
         * 回溯：如果当前选择不符合约束条件或者没有达到目标，算法将撤销最后的选择，回溯到上一步，然后尝试另一个选项。
         * <p>
         * 递归实现：回溯算法通常通过递归来实现，因为这样可以自然地模拟选择和撤销选择的过程。
         * <p>
         * 这种算法类似于在迷宫中探索所有可能的路径，一旦发现当前路径走不通，就退回到上一个分叉口尝试另一条路径。在计算机科学中，回溯算法被用于解决许多类型的问题，如八皇后问题、图的着色问题、组合问题等。
         *
         *
         */
        // 回溯算法的辅助方法
        private void backtrack(List<String> result, String digits, String current, int index, String[] mapping) {
            // 检查是否到达了数字字符串的末尾
            if (index == digits.length()) {
                // 将当前累积的字符串添加到结果列表中
                result.add(current);
                return;
            }

            // 获取当前数字对应的所有可能的字母
            String letters = mapping[digits.charAt(index) - '0'];
            // 遍历每个可能的字母
            for (int i = 0; i < letters.length(); i++) {
                // 继续回溯，考虑下一个数字，并将当前字母添加到累积的字符串中
                backtrack(result, digits, current + letters.charAt(i), index + 1, mapping);
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}